Contemporary map route planning systems can be characterized into two groups, those that are single-ended and those that are dual-ended. Both of these approaches rely on a map database that represents roads in terms of road segments. Typically, these road segments are stored in the map database that covers a geographical area including many road segments. Each road segment contained within the map database is typically defined in terms of two locations on the earth. Often these locations are coded in terms of latitude and longitude.
Route planning mechanisms, associated with the above-mentioned map route planning systems, search the map database for road segments that connect, or provide a traversable path between, a given origin location and destination location. For searching efficiency reasons the map databases are often coded into several layers, each representing progressive levels of detail of the represented road map. This type of map database is often referred to as a hierarchical map database.
Typically, these maps are constructed as follows. A lowest level (layer 0) would be coded to represent all known road segments located within a geographical area represented by the map database. Another level (layer 1) would be coded to represent the same geographical area as layer 0 but in a lower level of detail. For instance, on layer 1 all of the local road segments would be eliminated. Another level (layer 2) would be coded to represent the same geographical area as layer 1 but in yet another lower level of detail. For instance, on layer 2 all of the collector road segments would be eliminated. Another level (layer 3) would be coded to represent the same geographical area as layer 2 but in yet another lower level of detail. For instance, on layer 3 all of the arterial road segments would be eliminated. In this case layer 3 would only represent limited access, for instance highway, road segments.
In the case of dual-ended route planners, a solution may be found more quickly for small databases since the planning mechanism concurrently plans two routes each originating at the origin location and destination location hoping to meet in the middle. Although this method is typically faster in practice, it is also much more resource intensive. This is because the planning mechanism requires extracting road segments from two parts of the map database, significantly increasing temporary storage resources. Dual-ended route planning mechanisms also suffer when dynamic route characteristics are being considered. For instance, traffic density in terms of congestion may be available for an area proximate the origin location and the destination location. Since a path is simultaneously planned commencing from both the origin location and the destination location certain assumptions must be made regarding the time of arrival at the destination location. Because of this initial assumption the traffic congestion information may not match the actual traffic congestion present when the traveler actually arrives at the destination location.
In a single-ended route planning approach, by directing the route planning mechanism to start searching on the highest level (layer 3) first, a route between an origin and a destination may be found within a few iterations because there are only a relatively few road segments. Generally, the route planning mechanism commences with the origin location and queries the map database for all road segments connected to that origin. Next, if it found any, these road segments are expanded to include any successor road segments that progress towards the destination location. As is often the case, a route is not found at this highest level. When this happens the route planning mechanism will traverse downwardly to the next level of detail, here layer 2. Again the route planning mechanism continues planning by querying the map database at layer 2. This process is continued with further expansion of successor road segments and downward traversals until a route is connected between the origin and destination locations.
As a practical matter, this approach can be very resource intensive. So any improvement in this process is valuable. One problem with this approach can be illustrated with a brief example.
FIGS. 1a-1c illustrate a hierarchical map database covering a geographical area comprised two levels; layer 3 101 and layer 2 103. Here layer 3, similar to the layer 3 mentioned above, represents the coarsest level of the hierarchical map database. Also, just as mentioned above, layer 2 103 covers the same geographical area as layer 3 101 of the hierarchical map database but represents the geographical area in finer detail. Reference number 105 shows a route resulting from the prior art mapping approach. This routing result 105 is arrived at as follows.
An origin location 107 and a destination location 117, shown in the layer 3 map 101, are provided to the route planning mechanism as a prerequisite to the route planning process. Successor road segments 109, 111, 115 are expanded during the planning process, and thus a solution is found, using these successor road segments, to connect routes between the origin location 107 and the destination location 117. However, when viewing the next level of map detail, shown in layer 2 103, one can observe that a more optimal route, in terms of distance traversed, can be had. So, as can be seen by this example, the route planned as shown in the routing result box 105 is clearly less than optimal given the level of granularity available on layer 2 103 of the hierarchical map database. In other words if the route planning mechanism planned on layer 2, then a shorter route can be planned, albeit using more resources to plan the route because of the increased road segment density. This is because planning only at layer 2 103 requires consideration of more successor road segments which is less efficient in terms of quickly connecting the route between the origin location 107 and the destination location 117.
What is needed is a more efficient lower resource intensive and higher resulting route quality planner. This would preferably be compatible with a single-ended approach and have a means for traversing between layers to construct optimal routes in terms of allocating planning resources effectively and generating a shortest route.